package com.fufu.algorithem.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author: BlcakTiger
 * @date: 2023/2/26 10:44
 * @contact: hsf6661@163.com
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1,2,2,2,2,2,4};
        int res1 = searchByRecursion(arr, 0, arr.length-1, 4);
        System.out.println(res1);
        int res2 = search(arr, 4);
        System.out.println(res2);
    }

    /**
     * 递归方式
     * @param arr 数组
     * @param left 左边界
     * @param right 右边界
     * @param target 目标值
     * @return
     */
    public static int searchByRecursion(int[] arr,int left,int right,int target){
        int mid = (left+right)/2;

        if (left>right || right<left){
            return -1;
        }
        if (target > arr[mid]){
            return searchByRecursion(arr,mid+1,right,target);
        }else if (target < arr[mid]){
            return searchByRecursion(arr,left,mid-1,target);
        }else{
            return (left+right)/2;
        }
    }


    public static int search(int[] arr,int target){
        int left = 0;
        int right = arr.length;
        int mid = -1;
        while (right>=left){

            mid = (left+right)/2;

            if (target>arr[mid]){
                left = mid+1;
            }else if (target<arr[mid]){
                right = mid-1;
            }else {
                break;
            }
        }
        return mid;
    }
}
